#include <stdio.h>

#include "bitree.h"

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int MinDepth(BiTree t) {
    if (!t) {
        return 0;  // 若树为空，返回0
    }
    BiTree last = t;  // 记录当前层的最后一个结点
    int depth = 1;    // 记录当前结点的深度
    SqQueue q;
    InitQueue(&q);
    EnQueue(&q, t);  // 根结点入队
    while (!QueueEmpty(&q)) {
        BiTree p;
        DeQueue(&q, (void**)&p);  // 队头结点出队
        if (!p->lchild && !p->rchild) {
            return depth;  // 返回第一个叶子结点的深度
        }
        if (p->lchild) {
            EnQueue(&q, p->lchild);  // 如果有左孩子，将左孩子入队
        }
        if (p->rchild) {
            EnQueue(&q, p->rchild);  // 如果有右孩子，将右孩子入队
        }
        if (p == last) {                // 如果p是当前层的最后一个结点
            last = q.data[q.rear - 1];  // 更新last为下一层的最后一个结点
            ++depth;                    // 更新当前遍历结点的深度
        }
    }
    return depth;
}

void TestMinDepth(ElemType arr[], int n) {
    printf("test begin\n");

    BiTree root;
    LevelOrderCreateBiTree(&root, arr, n);
    printf("最小深度为：%d\n", MinDepth(root));

    printf("test end\n");
}

int main() {
    ElemType arr1[] = {'A'};
    TestMinDepth(arr1, 1);

    ElemType arr2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    TestMinDepth(arr2, 7);

    ElemType arr3[] = {'A', 'B', 'C', '#', '#', 'D', 'E', '#', 'F', '#', '#', 'G', '#', '#', '#'};
    TestMinDepth(arr3, 15);

    ElemType arr4[] = {'1', '2', '3', '4', '#', '5', '6', '#', '#', '7', '8', '9', 'A'};
    TestMinDepth(arr4, 13);

    return 0;
}